public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
}

 class Solution {
    //解法1：
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA = 0;
        int sizeB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        while (headA != null) {
            headA = headA.next;
            sizeA++;
        }
        while (headB != null) {
            headB = headB.next;
            sizeB++;
        }
        headA = curA;
        headB = curB;
        if (sizeA < sizeB) {
            int size = sizeB - sizeA;
            while (size != 0) {
                headB = headB.next;
                size--;
            }
        } else {
            int size = sizeA - sizeB;
            while (size != 0) {
                headA = headA.next;
                size--;
            }
        }
        while (headB != headA) {
            headB = headB.next;
            headA = headA.next;
        }
        return headA;
    }
    //解法2：巧妙的写法
     public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
         if(headA == null || headB == null) return null;
         ListNode n1 = headA;
         ListNode n2 = headB;

         while(n1 != n2){
             n1 = n1 == null ? headB : n1.next;
             n2 = n2 == null ? headA : n2.next;
         }
         return n1;
     }
     //解法3：哈希集合
}